package main

import (
	"fmt"
)

func main() {

	var en = [][]int{{1, 6}, {5, 4}, {6, 4}, {6, 7}, {2, 3}}
	arr := maxEnvelopes(en)
	fmt.Println(arr)

}

//n行m列的二维数组
func maxEnvelopes(envelopes [][]int) int {
	//边界条件判断
	if envelopes == nil || len(envelopes) == 0 {
		return 0
	}
	//先对信封进行排序
	for i := 0; i < len(envelopes); i++ {
		for j := 0; j < len(envelopes)-i-1; j++ {
			if envelopes[j][0] > envelopes[j+1][0] {
				envelopes[j][0], envelopes[j+1][0] = envelopes[j+1][0], envelopes[j][0]
				envelopes[j][1], envelopes[j+1][1] = envelopes[j+1][1], envelopes[j][1]
			}
		}

	}

	return lengthOfLIS(envelopes)

}

func lengthOfLIS(nums [][]int) int {
	max := 0
	dp := make([]int, len(nums))
	for m := 0; m < len(nums); m++ {
		dp[m] = 1
	}

	for i := 0; i < len(nums); i++ {
		for j := 0; j < i; j++ {
			if nums[i][1] > nums[j][1] {
				if dp[i] <= dp[j]+1 {
					dp[i] = dp[j] + 1
				}
				if max < dp[i] {
					max = dp[i]
				}

			}

		}

	}
	return max

}
